package LineCode.剑指Offer.递归和循环;

import org.apache.xmlbeans.impl.xb.xsdschema.impl.FacetImpl;

/**
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
 * n<=39
 */
public class 菲波那切数列 {



    public static void main(String[] args) {
        System.out.println(Fibonacci(4));
    }

    /**
     * 经典地柜题
     * @param n
     * @return
     */
    public static int Fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
